package class07;

/**
 * 设计一个打印整棵树的打印函数
 * 将树逆时针旋转90度打印较为方便(原样打印对齐比较复杂)
 * 思路:
 * 右 中 左 顺序打印
 */
public class Code05_PrintBinaryTree {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		//H表示头结点
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	/**
	 *
	 * @param head 当前来到哪个节点
	 * @param height 节点高度,预留多少空格
	 * @param to 节点身份 H-头, v-右树, ^-左树
	 * @param len 当前打印值占多大长度,默认17(考虑int长度及两个标识),        H1H       (H1H占了3个位置,剩下的左右各用7个空格补充)
	 */
	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		//v表示当前节点的父节点在下一行中寻找
		printInOrder(head.right, height + 1, "v", len);


		//处理打印
		//身份拼接
		String val = to + head.value + to;
		//中间位置
		int lenM = val.length();
		//计算左边补多少空格
		int lenL = (len - lenM) / 2;
		//计算右边补多少空格
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);


		//^表示当前节点的父节点在上一行中寻找
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(-222222222);
		head.right = new Node(3);
		head.left.left = new Node(Integer.MIN_VALUE);
		head.right.left = new Node(55555555);
		head.right.right = new Node(66);
		head.left.left.right = new Node(777);
		printTree(head);

		head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.right.left = new Node(5);
		head.right.right = new Node(6);
		head.left.left.right = new Node(7);
		printTree(head);

		head = new Node(1);
		head.left = new Node(1);
		head.right = new Node(1);
		head.left.left = new Node(1);
		head.right.left = new Node(1);
		head.right.right = new Node(1);
		head.left.left.right = new Node(1);
		printTree(head);

	}

}
